This paper studies networks with N half-duplex relays assisting thecommunication between a source and a destination. In ISIT'12 Brahma,\"{O}zg\"{u}r and Fragouli conjectured that in Gaussian half-duplex diamondnetworks (i.e., without a direct link between the source and the destination,and with N non-interfering relays) an approximately optimal relay schedulingpolicy (i.e., achieving the cut-set upper bound to within a constant gap) hasat most N+1 active states (i.e., at most N+1 out of the $2^N$ possible relaylisten-transmit states have a strictly positive probability). Such relayscheduling policies were referred to as simple. In ITW'13 we conjectured thatsimple approximately optimal relay scheduling policies exist for any Gaussianhalf-duplex multi-relay network irrespectively of the topology. This paperformally proves this more general version of the conjecture and shows it holdsbeyond Gaussian noise networks. In particular, for any memoryless half-duplexN-relay network with independent noises and for which independent inputs areapproximately optimal in the cut-set upper bound, an approximately optimalsimple relay scheduling policy exists. A convergent iterative polynomial-timealgorithm, which alternates between minimizing a submodular function andmaximizing a linear program, is proposed to find the approximately optimalsimple relay schedule. As an example, for N-relay Gaussian networks withindependent noises, where each node in equipped with multiple antennas andwhere each antenna can be configured to listen or transmit irrespectively ofthe others, the existence of an approximately optimal simple relay schedulingpolicy with at most N+1 active states is proved. Through a line-network exampleit is also shown that independently switching the antennas at each relay canprovide a strictly larger multiplexing gain compared to using the antennas forthe same purpose.
展开▼
